|
グラフ理論において、ケージとは与えられた与えられた内周を満たす正則グラフのうち、頂点数が最小のものである。 厳密に述べると次のようになる。(''r'',''g'')-グラフとは任意の頂点が相異なる''r''個の頂点と隣接し、かつグラフに含まれる最小のサイクルの長さが''g''に一致するものを指す。任意の''r'' ≥ 2、''g'' ≥ 3に対して(r,g)-グラフは存在することが知られている。(''r'',''g'')-ケージとは(''r'',''g'')-グラフのうちもっとも頂点数が少ないグラフのことである。 次数''r''、内周gのムーアグラフは存在すれば、ケージとなる。ムーアグラフの頂点数を表す式はケージに対して一般化することができる。すなわち奇内周gをもつグラフの頂点数は : 以上となる。任意の(r,g)-グラフが上述の式を満たすと、定義からムーアグラフとなり、またケージとなる。同様に偶内周の場合は頂点数は : 以上となる。また''r''と''g''の組み合わせによっては複数の同型でないケージが存在しうる。例えば、頂点数70となる(3,10)-ケージはバラバン10-ケージ、Harries graphとHarries-Wong graphの同型でない三つが存在する。一方で (3,11)-ケージは頂点数が112となるバラバン11-ケージのみである。 == 具体例 == 次数1のグラフはサイクルを持たない。次数2のグラフはサイクルそのもので内周は頂点数に一致する。そのため''r'' ≥ 3の場合についてケージを考える。(''r'',3)-ケージは頂点数r+1の完全グラフ''K''''r''+1となる。また(''r'',4)-ケージは頂点数2''r''の完全二部グラフ''K''''r'',''r''となる。 他の特筆すべきケージ（ムーアグラフを含む。）: * (3,5)-ケージ: ピーターセングラフ、頂点数10 * (3,6)-ケージ: ヒーウッドグラフ、頂点数14 * (3,8)-ケージ: Tutte–Coxeter graph、頂点数30 * (3,10)-ケージ: バラバン10-ケージ、頂点数70 * (4,5)-ケージ: ロバートソングラフ、頂点数19 * (7,5)-ケージ: ホフマン-シングルトングラフ、頂点数50 * ''r''-1が素数のべき乗のとき、(''r'',6)-ケージは射影平面のインシデント・グラフとなる。 * ''r''-1が素数のべき乗のとき、(''r'',8)-ケージと(''r'',12)-ケージは一般化多角形となる。 ''r'' > 2かつ''g'' > 2の場合に知られている(''r'',''g'')-ケージの頂点数を次表にまとめる。ただし射影平面と一般化多角形によるものは除く。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ケージ (グラフ理論)」の詳細全文を読む スポンサード リンク
|